package cn.kuick.match3.test1;

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author 春凡
 * 
 * 删除重复的字母（Remove Duplicate Letters）
 * 给定一个只包含小写字母的字符串，从中移除重复字母使得每个字母只出现一次。你必须确保你的结果是所有可能的结果最小的字典序。
 *（Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once.
 *You must make sure your result is the smallest in lexicographical order among all possible results.）
 * 示例：
 * 给定字符串："bcabc"，返回："abc"
 * 给定字符串："cbacdcbc"，返回："acdb"64
 */
public class RemoveDuplicateLetters_fan {
	
	
	public static void main(String[] args) {
		
		findSmallestLetter("ccaecbbdda");
		
	}
	
	private static void findSmallestLetter(String source){
		List<String> list = new ArrayList<>();
		removeDuplcateLetter(source, list); 
		
		String smallestString = list.get(0);
		System.out.println(smallestString); 
		for (int i = 1; i < list.size(); i++) {
			String string = list.get(i);
			System.out.println(string); 
			if(string.compareTo(smallestString)<0){
				smallestString = string;
			}
		}
		
		System.out.println("smallest string is = "+smallestString+"  ,list size = "+list.size()); 
	}
	
	private static void removeDuplcateLetter(String source,List<String> list){
		
		//判断是否有相同字符
		Point point = haveEqualChar(source); 
		
		if(point == null){
			
			//无相同字符
			list.add(source);
			
		}else if(point.y -point.x == 1){
			
			//如果两个相等字符相邻，那么直接删除其中一个即可(这个判断很重要)
			source = source.substring(0,point.x).concat(source.substring(point.x+1)); 
			removeDuplcateLetter(source, list); 
			
		}else {
			//有相同字符
			
			//删除point.x，point.y 位置字符
			String temp1 = source.substring(0, point.x).concat(source.substring(point.x+1));
			String temp2 = source.substring(0, point.y).concat(source.substring(point.y+1));
			
			//循环执行
			removeDuplcateLetter(temp1,list);
			removeDuplcateLetter(temp2,list); 
			
		}
	}
	
	
	//判断字符串中是否有相同的字符，如果有，返回两个相同字符的下标
	private static Point haveEqualChar(String source){
		
		// 从下标0开始遍历
		for (int i = 0; i < source.length(); i++) {
			
			Character charA = source.charAt(i); 
			
			//从下标为 i+1 开始遍历
			for (int j = i+1; j < source.length(); j++) {
				
				Character charB = source.charAt(j); 
				
				//如果两个字符相等，返回两个字符的下标，不再往后遍历，即使后面还有相同的字符
				if(charA.equals(charB)){
					
					return new Point(i, j); 
				}
			}
			
		}
		
		return null;
	}
}
